package leetcode.双指针法;

/**
 * 寻找重复数
 * https://leetcode-cn.com/problems/find-the-duplicate-number/
 * 给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [1,3,4,2,2]
 * 输出: 2
 */
public class Test287 {

    /**
     * 弗洛伊德循环探测算法：
     * 先判断数组里面是否存在重复的数据，然后再从重复的位置开始再次探测，再次探测中第一次相遇的位置就是重复出现的数字
     *
     * @param nums
     * @return
     */
    public static int findDuplicate(int[] nums) {
        if (nums.length == 0)
            return 0;
        // 乌龟指针，每次只走一步
        int tortoise = nums[0];
        // 兔子指针，每次走两步
        int hare = nums[0];
        while (true) {
            tortoise = nums[tortoise];
            hare = nums[nums[hare]];
            if (tortoise == hare) { // 检测是否发生了环
                break;
            }
        }
        // p1 从0开始，p2从相遇的地方开始，每次都只走一步，寻找第一次相遇的位置
        int p1 = nums[0];
        int p2 = tortoise;
        while (p1 != p2) {
            p1 = nums[p1];
            p2 = nums[p2];
        }
        // 返回相遇的位置数值
        return p1;
    }

    public static void main(String[] args) {
//        int[] a = {1, 3, 4, 0, 2, 5};
        int[] a = {1, 4, 6, 2, 6, 3, 5};
        System.out.println(findDuplicate(a));
    }
}
